רשימת דילוגים (skip list):

• הוא מימוש של dynamic set עם הסיבוכיות זמן הבאות:
  • חיפוש והכנסה : $\mathrm{\Theta }logn$
  • מחיקה: $\mathrm{\Theta }1$
  • מינימום, מקסימום, Successor (יורש), Predecessor (קודם): $\mathrm{\Theta }1$

מבנה הרשימה:

• רשימת דילוגים S מכילה $S_n$ רשימה מקושרת דו כיוונית ממויינת כך ש:
  • הרשימה $S_0$ מכילה את כל האיברים של S
  • הרשימה $S_i$ מכילה את כל האיברים של $S_{i-1}$ בהסתברות של 0.5
  • כל רשימה מכילה תא סנטינל שמחזיק מצביע לאלמנט הראשון של אותה רשימה (והאלמנט הראשון מחזיק מצביע לסנטינל).
  • במקום לשמור מספר תאים (Nodes) עבור כל איבר של S, שומרים רק תא אחד עבור כל איבר, כאשר לכל תא יש את הערכים הבאים:
    • המפתח(x.key)
    • הגובה(x.h): מוגדר כ i המקסימלי שעבורו x שייך ל $S_i$
    • מערך(x.next): מערך בגודל h + 1 שמכיל מצביעים לתאים שבאים אחרי x ברשימות $S_0,...,S_{x.h}$
    • מערך (x.prev): בערך בגודל h +1
  • גובה הרשימה: הגובה של הסנטינל, הוא גם הגובה המקסימלי של שאר התאים.
  • 

הגודל הצפוי (תוחלת גודל הרשימה):

• תוחלת מספר התאים ברשימת דילוגים המכילה n איברים (לא כולל תאי סנטינל) היא 2n.
• הרעיון המרכזי:
  • ההסתברות שאיבר מסוים $x$ יופיע ברמה $S_i$ היא $\frac{1}{2^i}$.
  • גודל הרמה $S_i$ (מספר האיברים בה) מתפלג בינומית עם הפרמטרים $n$ ו-$\frac{1}{2^i}$ ולכן תוחלת מספר האיברים ברמה $S_i$ היא: $E[|S_i|]=\frac{n}{2^i}$.
  • תוחלת מספר הצמתים הכולל מתקבלת מסכום התוחלות של כל הרמות (מ-$i=0$ עד $\mathrm{\infty }$):
  • $$E[\sum _{i=0}^{\mathrm{\infty }}|S_i|]=\sum _{i=0}^{\mathrm{\infty }}\frac{n}{2^i}=n\sum _{i=0}^{\mathrm{\infty }}\frac{1}{2^i}=n\cdot 2=2n$$

הגובה הצפוי (תוחלת גובה הרשימה):

• תוחלת הגובה של רשימת הדילוגים היא לכל היותר $log(n)+2$ .
• הרעיון המרכזי:

  • מגדירים משתנה מקרי מציין (Indicator) $X_i$ לכל רמה $i\ge 1$, המקבל את הערך $1$ אם הרמה אינה ריקה, ו-$0$ אם היא ריקה.

  • גובה הרשימה $h$ הוא סכום המשתנים המציינים: $h=\sum _{i=1}^{\mathrm{\infty }}{X}_i$.

  • מכיוון ש-$X_i\le |S_i|$, מתקיים $E[X_i]\le \frac{n}{2^i}$. כמו כן, מכיוון ש-$X_i\le 1$, מתקיים תמיד $E[X_i]\le 1$.

  • מפצלים את סכום התוחלות לשני חלקים – עד הרמה ה-$\lfloor \log n\rfloor$ , וממנה והלאה (מכיוון ש אם נציב $i={\log }_{2}n$ בתוחלת מספר האיברים, נקבל שתוחלת מספר האיברים ברמה הזו היא בדיוק: $\frac{n}{2^{{\log }_{2}n}}=\frac{n}{n}=1$):

    • בחלק הראשון (עד $\log n$) חוסמים את התוחלת ב-$1$ (מקסימום $\log n$ רמות).
    • בחלק השני (מרמה $\log n+1$ ואילך) משתמשים בחסם $\frac{n}{2^i}$, וסכום הטור ההנדסי שמתקבל חסום ב-$2$.

  • סה"כ מקבלים: $E[h]\le \log n+2$.

הגודל הצפוי (כולל זקיפים):

• תוחלת מספר הצמתים הכולל ברשימה (כולל צמתי הזקיף) היא $2n+O(\log n)$.
• הרעיון המרכזי:
  • מספר הצמתים הרגילים בתוחלת הוא $2n$.
  • בכל רמה יש סנטינל אחד. מכיוון שתוחלת הגובה חסומה ב-$\log n+2$, תוחלת מספר הסנטינלים חסומה ב-$(\log n+2)+1$ (כולל רמת הבסיס).
  • לכן, תוספת הסנטינלים לגודל הרשימה היא בסדר גודל של $O(\log n)$, והגודל הכולל נשאר ליניארי: $2n+O(\log n)$.